package com.darrenchan.leetcode;

import java.util.HashSet;
import java.util.Set;

/**
 * @Desc
 * @Author chenchi03
 * @CreateTime 2019-12-25 16:28
 */
public class Q37 {

    public void solveSudoku(char[][] board) {
        if(isSuccess(board)) {
            return;
        }

        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if(board[i][j] != '.') {
                    continue;
                }

                for (int k = 1; k <= 9; k++) {
                    board[i][j] = (char)(k + '0');
                    if(isValid(board, i, j)) {
                        solveSudoku(board);
                    }
                    board[i][j] = '.';
                }
            }
        }
    }

    private boolean isSuccess(char[][] board) {
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if(board[i][j] == '.') {
                    return false;
                }
            }
        }
        return true;
    }

    private boolean isValid(char[][] board, int a, int b) {
        Set<Character> contained = new HashSet<Character>();
        for (int j = 0; j < 9; j++) {
            if (contained.contains(board[a][j])) return false;
            if (board[a][j] > '0' && board[a][j] <= '9')
                contained.add(board[a][j]);
        }


        contained = new HashSet<Character>();
        for (int j = 0; j < 9; j++) {
            if (contained.contains(board[j][b])) {
                return false;
            }
            if (board[j][b] > '0' && board[j][b] <= '9') {
                contained.add(board[j][b]);
            }
        }


        contained = new HashSet<Character>();
        for (int m = 0; m < 3; m++) {
            for (int n = 0; n < 3; n++) {
                int x = a / 3 * 3 + m, y = b / 3 * 3 + n;
                if (contained.contains(board[x][y])) {
                    return false;
                }
                if (board[x][y] > '0' && board[x][y] <= '9') {
                    contained.add(board[x][y]);
                }
            }
        }

        return true;
    }

}
